import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
 * @lc app=leetcode.cn id=721 lang=java
 *
 * [721] 账户合并
 */

// @lc code=start
class Solution {
    //我个人感觉这道题可以划到困难，因为用并查集写是有点麻烦的                                         
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String,Integer> emailToIndex = new HashMap<>();//映射邮箱对应的编号（即所属的集合）
        Map<String,String> emailToName = new HashMap<>();//映射邮箱对应的姓名
        int emailCount = 0;//记录邮箱数目

        for(List<String> account : accounts){
            String name = account.get(0);//拿到姓名
            int accountSize = account.size();
            for(int i = 1 ;i<accountSize;i++){//拿到邮箱
                String emailName = account.get(i);
                if(!emailToIndex.containsKey(emailName)){//不需要放相同的email
                    emailToIndex.put(emailName, emailCount++);
                    emailToName.put(emailName, name);
                }
            }
            //这样拿到的emailCount即是不重复的邮箱的数目-1。
        }

        UnionFind uf = new UnionFind(emailCount);//刚好不会数组越界
        for(var account : accounts){
            String firstEmail = account.get(1);//第一个邮箱
            int firstIndex = emailToIndex.get(firstEmail);//第一个邮箱对应的index，将它作为父节点，来代表这个联通分量。
            int size = account.size();
            for(int i =2 ;i<size;i++){//从第二个邮箱遍历起
                String nextEmail = account.get(i);
                int nextIndex = emailToIndex.get(nextEmail);
                uf.union(firstIndex, nextIndex);//主要是把index给并在一起，email主要是用来查index的
            }
        }
        Map<Integer,List<String>> indexToEmail = new HashMap<>();//把同一个类的email放在一起
        for(String email : emailToIndex.keySet()){//这个循环就是写满indexToEmail
            //不是直接放这个email对应的index，放其对应的父节点类的index。
            int index = uf.find(emailToIndex.get(email));
            List<String> account = indexToEmail.getOrDefault(index, new ArrayList<>());//如果找的到index就放index对应的email集合进去
            account.add(email);
            indexToEmail.put(index, account);
        }
        //然后在indexToEmail前面需要加一个名字即可
        List<List<String>> ans = new ArrayList<>();
        for(var emails : indexToEmail.values()){
            Collections.sort(emails);//先排个序
            //拿到名字往emails前面一塞
            String name = emailToName.get(emails.get(0));
            //往前加比较麻烦，重开一个
            List<String> temp = new ArrayList<>();
            temp.add(name);
            temp.addAll(emails);
            ans.add(temp);
        }
        return ans;
    }

    class UnionFind{
        int parent[];

        public UnionFind(int n){
            this.parent = new int[n];
            for(int i=0;i<n;i++){
                parent[i]=i;//先赋初值
            }
        }

        public int find(int x){
            return parent[x]==x ? x : find(parent[x]);
        }

        public void union(int x ,int y){
            //合并x,y。即找到其父节点，然后合并。这里默认指向x的父节点。
            parent[find(y)]= find(x);
        }
    }
}
// @lc code=end

